iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 11
0
自我挑戰組

練習程式系列 第 11

java,單向連結串列

  • 分享至 

  • xImage
  •  

看網路上大大們的文章和影片,做些紀錄。
以下內容來自網路上大大們的文章。
紀錄單向連結串列的程式來源。 稍微修改,print 觀察

教學來源:
Introduction to linked list

程式來源:
連結串列(Linked List)

abstract class LinkedList < T > {
 protected int count;
 protected Node < T > first;
 protected Node < T > last;
 public Node < T > getFirst() {
  return first;
 }
 public Node < T > getLast() {
  return last;
 }
 abstract public void addAfter(Node < T > node, T value);
 abstract public void removeFirst();
 abstract public void removeLast();
 abstract public void remove(Node < T > node);
 abstract public void print();
 abstract public void rev();
}


class Node < T > {
 private Node < T > next;
 private T value;

 public Node < T > getNext() {
  return next;
 }

 void setNext(Node < T > next) {
  this.next = next;
 }

 public T getValue() {
  return value;
 }

 void setValue(T value) {
  this.value = value;
 }

 public Node(T value) {
  this.value = value;
 }
}


class SinglyLinkedList < T > extends LinkedList < T > {
 public void addFirst(T value) {
  // TODO Auto-generated method stub
  Node < T > node = new Node < T > (value);
  if (count == 0)
   last = node;
  else
   node.setNext(first);
  first = node;
  ++count;
 }

 @Override
 public void addAfter(Node < T > node, T value) {
  // TODO Auto-generated method stub
  Node < T > newNode = new Node < T > (value);
  newNode.setNext(node.getNext());
  node.setNext(newNode);
  if (node == last) {
   last = newNode;
  }
  ++count;
 }

 @Override
 public void removeFirst() {
  // TODO Auto-generated method stub
  if (count == 0)
   throw new ArrayIndexOutOfBoundsException();
  else if (count == 1) {
   first = null;
   last = null;
  } else {
   Node < T > node = first.getNext();
   first.setNext(null);
   first = node;
  }
  --count;
 }

 @Override
 public void removeLast() {
  // TODO Auto-generated method stub
  if (count == 0)
   throw new ArrayIndexOutOfBoundsException();
  else if (count == 1) {
   first = null;
   last = null;
  } else {
   Node < T > node = findPreviousNode(last);
   node.setNext(null);
   last = node;
  }
  --count;
 }

 @Override
 public void remove(Node < T > node) {
  // TODO Auto-generated method stub
  if (node == first)
   removeFirst();
  else if (node == last)
   removeLast();
  else {
   Node < T > preNode = findPreviousNode(node);
   if (preNode == null)
    throw new ArrayIndexOutOfBoundsException();
   preNode.setNext(node.getNext());
   node.setNext(null);
   --count;
  }
 }

 private Node < T > findPreviousNode(Node < T > node) {
  Node < T > preNode = first;
  while (preNode != null) {
   if (node == preNode.getNext())
    break;
   preNode = preNode.getNext();
  }
  return preNode;
 }

 public void print() {
  Node printTemp = first;
  while (printTemp != null) {
   System.out.print(printTemp.getValue());
   printTemp = printTemp.getNext();
   if (printTemp != null) System.out.print(" --> ");
   else System.out.println();
  }

 }

 public void rev() {
  Node a = null, b = null;
  while (first != null) {
   a = b;
   b = first;
   first = first.getNext();
   b.setNext(a);
   //print();
   if (first == null) {
    first = b;
    break;
   }
  }
  //	print();
 }

}


class Main {
 public static void main(String[] args) {
  SinglyLinkedList singlyLinkedList = new SinglyLinkedList();
  singlyLinkedList.addFirst(1);
  singlyLinkedList.addFirst(12.34);
  singlyLinkedList.addFirst("ABCD");
  singlyLinkedList.print(); //ABCD --> 12.34 --> 1
  //顛倒
  singlyLinkedList.rev();
  singlyLinkedList.print(); //1 --> 12.34 --> ABCD

  singlyLinkedList.remove(singlyLinkedList.getFirst().getNext());
  singlyLinkedList.print(); //1 --> ABCD

  singlyLinkedList.addAfter(singlyLinkedList.getFirst().getNext(), 12);
  singlyLinkedList.print(); //1 --> ABCD --> 12
 }
}
ABCD --> 12.34 --> 1
1 --> 12.34 --> ABCD
1 --> ABCD
1 --> ABCD --> 12

上一篇
android 簡介
下一篇
java,雙向連結串列
系列文
練習程式37
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言